// 2025/5/29
// 取金币

#include <functional>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param coins int整型vector
     * @return int整型
     */
    int getCoins(vector<int>& coins) {
        // write code here
        int n = coins.size();
        vector<int> cost(n + 2, 1);
        for (int i = 1; i <= n; i++) 
        {
            cost[i] = coins[i - 1];
        }

        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for(int gap = 0; gap < n; gap++)
        {
            for(int i = 1, j = i + gap; j <= n; i++, j++)
            {
                for(int k = i; k <= j; k++)
                {
                    dp[i][j] = max(dp[i][j], cost[i - 1] * cost[k] * cost[j + 1] + 
                    dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }
        return dp[1][n];
    }
};